#leetcode题目46：全排列
#难度：中等
#时间复杂度：O(n!)
#空间复杂度：O(n!)
#方法：回溯

from typing import List
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return []
        visited=[False]*len(nums)
        res=[]


        def dfs(res,path,depth,visited):
            if depth==len(nums):
                res.append(path[:])
                return
            for i in range(len(nums)):
                if not visited[i]:
                    visited[i]=True
                    path.append(nums[i])
                    dfs(res,path,depth+1,visited)
                    path.pop()
                    visited[i]=False

        dfs(res,[],0,visited)
        return res

#测试数据
nums=[1,2,3]
#预期输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
solution=Solution()
print(solution.permute(nums))

nums=[0,1]
#预期输出：[[0,1],[1,0]]
solution=Solution()
print(solution.permute(nums))

nums=[1]
#预期输出：[[1]]
solution=Solution()
print(solution.permute(nums))